#include "svd.h"

#include <vector>
#include <string.h>
#include <math.h>
#include <ext/hash_map>

#include <ext/hash_set>
#include <fstream>

#include "gbk.h"
#include "slog.h"
#include "Config.h"

using namespace std;
using namespace d_utils;
using __gnu_cxx::hash_map;
using __gnu_cxx::hash_set;

double SVDTrainer::mult_ij(matrix_t& P, matrix_t& Q, const int i, const int j)
{
	double ret = 0;
	for(int m=0; m<dim; m++) ret += P[i][m]*Q[j][m];
	return ret;
}

double SVDTrainer::RMSE(hash_map<int, vector<int> > &real_map, matrix_t& P, matrix_t& Q)
{
	double score_sum = 0, base_sum = 0;
	for(hash_map<int, vector<int> >::iterator it = real_map.begin(); it != real_map.end(); it++)
	{
		base_sum+=(it->second).size();
		for(vector<int>::iterator itt = (it->second).begin(); itt != (it->second).end(); itt++)
		{
			score_sum += pow(1-mult_ij(P, Q, key2x[it->first], key2y[*itt]), 2);
		}
	}
	return sqrt(score_sum/base_sum);
}

SVDTrainer::SVDTrainer(hash_map<int, vector<int> >&real_map, const int dimension, const double k1, const double k2)
{
	Info("real map size %d", real_map.size());
	kx = ky = 0.01;
	if(dimension > 0) dim = dimension;
	else dim = 10;
	if(k1 > 0 && k1 < 1) kx = k1;
	if(k2 > 0 && k2 < 1) ky = k2;
	l_rate = 0.01;
	xmax=ymax=0;

	for(hash_map<int, vector<int> >::iterator it = real_map.begin(); it != real_map.end(); it++)
	{
		key2x[it->first] = xmax;
		for(vector<int>::iterator itt = (it->second).begin(); itt != (it->second).end(); itt++)
		{
			if(key2y.find(*itt) == key2y.end())
			{
				key2y[*itt] = ymax;
				ymax++;
			}
		}
		xmax++;
	}
	U.resize(xmax);
	for(int i=0; i<xmax; i++) 
	{
		U[i].resize(dim);
	}
	M.resize(ymax);
	for(int i=0; i<ymax; i++) 
	{
		M[i].resize(dim);
	}
	Info("init with xmax=%d ymax=%d", xmax, ymax);
}

void SVDTrainer::init(hash_map<int, vector<int> > &i2w, hash_map<int, vector<int> > &w2i)
{
	double base = sqrt(dim);
	time_t t;
	srand(time(&t));
	for(int i=0; i<ymax; i++)
	{
		for(int j=0; j<dim; j++) 
		{
			U[i][j] = rand()/double(RAND_MAX+1)/base;
		}
	}
	for(int i=0; i<ymax; i++)
	{
		for(int j=0; j<dim; j++) 
		{
			M[i][j] = rand()/double(RAND_MAX+1)/base;
		}
	}
	Info("finish init");
}


row_t SVDTrainer::gradient(const int i, const int j, const double k, matrix_t &P, matrix_t &Q)
{
	row_t ret;
	ret.resize(dim);
	for(int n=0; n<dim; n++)
	{
		ret[n] = (1 - mult_ij(P, Q, i, j))*Q[j][n] - k * P[i][n];
	}
	return ret;
}

void SVDTrainer::update(matrix_t &P, row_t &r, const int i)
{
	for(int j=0; j< dim; j++)
	{
		P[i][j] += l_rate*r[j];
	}
}

void SVDTrainer::train(hash_map<int, vector<int> > real_map, const double learning_rate, const int max_step)
{
	if( 0 < learning_rate && 1 > learning_rate) l_rate = learning_rate;
	double last_rmse = INT_MAX;
	int step = 0;
	hash_map<int, vector<int> >::iterator xiter = real_map.begin();
	vector<int>::iterator yiter = (xiter->second).begin();
	while( step < max_step)
	{
		if(key2x.find(xiter->first) != key2x.end() &&
				key2y.find(*yiter) != key2y.end())
		{
			Info("%d",step);
			int x = key2x[xiter->first];
			int y = key2y[*yiter];
			row_t GU = gradient(x, y, kx, U, M);
			row_t GM = gradient(x, y, ky, M, U);
			update(U, GU, x);
			update(M, GM, y);
			double rmse = RMSE(real_map, U, M);
			Info("%.10lf", rmse);
			step++;
			if( rmse > last_rmse) break;
			else 
				last_rmse = rmse;
		}
		if(yiter == (xiter->second).end()-1)
		{
			if(xiter == real_map.end())
			{
				Info("trained all data");
				xiter = real_map.begin();
				yiter =  (xiter->second).begin();
			}
			else xiter++;
		}
		else yiter++;
	}
}

SVDTrainer::SVDTrainer()
{
}

SVDTrainer::~SVDTrainer()
{
}

bool operator < (const Itemscore& left, const Itemscore& right)
{
	return left.score > right.score;
}

vector<Itemscore> SVDTrainer::yield_item(int item, int size)
{
	vector<Itemscore> scores;
	for(hash_map<int, int>::iterator it = key2y.begin(); it!=key2y.end(); it++)
	{
		double score = mult_ij(U, M, key2x[item], it->second);
		//Info("%d %d | %d %d | %lf", item, key2x[item], it->first, it->second, score);
		Itemscore is;
		is.item = it->first;
		is.score = score;
		scores.push_back(is);
	}
	sort(scores.begin(), scores.end());
	scores.resize(size);
	return scores;
}
